package com.ma.ExtendedAlgorithm;

public class extra {

    /**
     * 在含有偶数个n种数和奇数个的两种数a、b的数组中找到a、b
     * @param arr
     */
    public static void extra_01(int[] arr){
        int eor=0;
        /**
         * 将这组数组相互异或，偶数就是0只留下了奇数的那两个即arr[0]^arr[1]^...^arr[i]==a^b;
         * 如:
         *  00010010
         * ^00001111
         * =00011101
         */
        for(int i=0;i<arr.length;i++){
            eor^=arr[i];
        }
        /**
         * 取出该异或结果，通过该算法{eor&(~eor+1)}获取最右侧的1
         *
         * 即00011101中最右侧的1那么这个1一定是a、b只有一个有的
         */
        int RightOne=eor&(~eor+1);
        int only=0;
        for(int i=0;i<arr.length;i++){
            /**
             * 将这组数再次异或，但是只有与那个最右侧的1进行与运算不为0(即所以该位仍为1的数)才进行异或运算并重新记录
             * 这样其中一个奇数和一些偶数个的某数就可以异或了即a就找到了，only=c^c^c^c^...^d^d^a=a
             * 最后在eor^only=a^b^only=b
             */
            if((arr[i]&RightOne)!=0){
                only^=arr[i];
            }
        }
        System.out.println("a:"+only+",b:"+(eor^only));
    }

}
